package algorithm;

/**
 * @author fangkun
 * @create 2022-05-19-10:09
 *
 * 134
 */
public class GasStation {
    public static void main(String[] args) {
        int[] gas = new int[]{1,2,3,4,5};
        int[] cost = new int[]{3,4,5,1,2};

        int i = canCompleteCircuit(gas, cost);
        System.out.println(i);
    }

    static int canCompleteCircuit(int[] gas, int[] cost) {

        int n = gas.length;
        //相当于图像中的坐标点和最低点
        int sum = 0, minSum = 0;
        int start = 0;

        for (int i = 0; i < n; i++) {
            sum += gas[i] - cost[i];
            if (sum < minSum) {
                // 经过第 i 个站点后，使 sum 到达新低
                // 所以站点 i + 1 就是最低点（起点）
                start = i + 1;
                minSum = sum;
            }
        }
        if (sum < 0) {
            // 总油量⼩于总的消耗，⽆解
            return -1;
        }
        // 环形数组特性
        return start == n ? 0 : start;
    }
}
